import java.util.Stack;

public class Path
{
    private static final int UNKNOW=-1;

    Case[][] map;
    
    public int largeur; //Exprimé en nombre de cases.
    public int hauteur; //idem

    //Need bouger ces trucs ailleurs, car cela sous-entend que l'on ne peut faire qu'un pathFiding à la fois o_O
    private Case[]Util; //Cases adjacentes à la case courante.
    public QueueDeCase openList;

    //Constructeur pour un terrain vide
    public Path(int largeur, int hauteur /*,int[]Terrain*/  )
    {

	this.largeur=largeur;
	this.hauteur=hauteur;
	this.map=new Case[largeur][hauteur];
	this.Util=new Case[8];

	for(int i=0; i<largeur; i++)
	    for(int j=0; j<hauteur; j++)
		this.map[i][j]=new Case(i,j);

	openList=new QueueDeCase();	    
    }

    //Constructeur pour un terrain ou l'on connait des emplacements d'obstacles.
    public Path(int largeur, int hauteur, int[]Obstacles)
    {
	this(largeur, hauteur);

	if(Obstacles!=null)
	    if(Obstacles.length%2!=0)
	    	System.out.println("Le tableau du terrain est probablement mal écrit");
	    else
		for(int i=0; i<Obstacles.length; i+=2)
		    this.map[Obstacles[i]][Obstacles[i+1]].Walkable=false;
		     
    }

    private void reinitUtil()
    {
	for(int i=0; i<8; i++)
	    this.Util[i]=null;    
    }

    private void avoirCarreAdj(int x, int y)
    {
	this.reinitUtil();

	if(y!=0 && x!=0 && this.map[x-1][y-1].Walkable && !this.map[x-1][y-1].isClosed)
	    this.Util[0]=this.map[x-1][y-1];
	    
	if(y!=0 && this.map[x][y-1].Walkable && !this.map[x][y-1].isClosed)
	    this.Util[1]=this.map[x][y-1];
	    
	if(y!=0 && x!=this.largeur-1 && this.map[x+1][y-1].Walkable && !this.map[x+1][y-1].isClosed)
	    this.Util[2]=this.map[x+1][y-1];		    
	    
	if(x!=this.largeur-1&& this.map[x+1][y].Walkable && !this.map[x+1][y].isClosed)
	    this.Util[3]=this.map[x+1][y];
	    
	if(x!=this.largeur-1 && y !=this.hauteur-1&& this.map[x+1][y+1].Walkable && !this.map[x+1][y+1].isClosed)
	    this.Util[4]=this.map[x+1][y+1];
	    
	if(y!=this.hauteur-1 && this.map[x][y+1].Walkable && !this.map[x][y+1].isClosed)
	    this.Util[5]=this.map[x][y+1];
	    
	if(y!=this.hauteur-1 && x!=0 && this.map[x-1][y+1].Walkable && !this.map[x-1][y+1].isClosed)
	    this.Util[6]=this.map[x-1][y+1];
	    
	if(x!=0 && this.map[x-1][y].Walkable && !this.map[x-1][y].isClosed)
	    this.Util[7]=this.map[x-1][y];    
    }

    public void TraitementDesCarresAdjacents(Case caseCourante,int xGoal, int yGoal)
    {
	int x=caseCourante.x;
	int y=caseCourante.y;

	avoirCarreAdj( x, y);
	for(int i=0; i<8; i++)
	    if( (this.Util[i]!=null) )

		if(!this.Util[i].isOpen){

		    caseCourante.setALLcost(this.Util[i], xGoal, yGoal);
		    this.openList.addToQueue(this.Util[i]);
		    this.Util[i].father=caseCourante;
		}
		    
	        //Ce qui veut dire que la case est présente dans la open list
		else{
		    int Fsvg= this.Util[i].Fcost;
		    int Gsvg= this.Util[i].Gcost;
		    int Hsvg= this.Util[i].Hcost;

		    /*Si cette case est présente dans la openList, cela veut dire :
		        > cette case est dans un chemin potentiel.
		        > cette case a de plus un père différent de la case courante
		        > On peut alors se poser la question : est-ce que le cout du chemin pour aller à cette case est 
			optimal, ou peut-il etre améliorer en venant de la case courante ?*/
		    caseCourante.setALLcost(this.Util[i], xGoal, yGoal);
		    
		    if(this.Util[i].Fcost < Fsvg ){
			//Le chemin peut etre amélioré
			//On enlève, puis on enfile, pour reclasser la liste, car les F ne sont plus bons.
			this.openList.removeFromQueue(this.Util[i]);
			this.Util[i].father=caseCourante;
			this.openList.addToQueue(this.Util[i]);
			
		    }

		    //Le chemin n'est pas meilleur, on rétablit les cost.
		    else{
			this.Util[i].Fcost = Fsvg;
			this.Util[i].Gcost = Gsvg;
			this.Util[i].Hcost = Hsvg;
		    }
		}
    }

    public void Path(Case start, Case goal)
    {
	Case caseCourante=start;
	caseCourante.isOpen=false;
	caseCourante.isClosed=true;

	while(caseCourante!=goal)
	    {
		TraitementDesCarresAdjacents(caseCourante, goal.x, goal.y);
		caseCourante=openList.defiler();
		caseCourante.isOpen=false;
		caseCourante.isClosed=true;
	    }
    }

    public void afficherSolution(Case start, Case goal)
    {
	System.out.println("Start : "+start.x+", "+start.y);
	System.out.println("Goal : "+goal.x+", "+goal.y);
	System.out.println("");
	System.out.println("");

	Stack st=new Stack();
	
	//st.push(goal);

	//WOOT LOL CRADE
	String[][]mapTMP=new String[largeur][hauteur];
	for(int i=0; i<this.largeur; i++)
	    for(int j=0; j<this.hauteur; j++)
		if(!this.map[i][j].Walkable)
		    mapTMP[i][j]="X";
		else
		    mapTMP[i][j]=".";

	while(start.x!=goal.x || start.y!=goal.y)
	    {
		mapTMP[goal.x][goal.y]="O";
		goal=goal.father;
	    }
	mapTMP[goal.x][goal.y]="O";

	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    System.out.print( mapTMP[j][i]+" ");
		System.out.println("");
	    }
    }

    public Stack Solution(Case start, Case goal)
    {
	Stack st=new Stack();
	while(start.x!=goal.x || start.y!=goal.y)
	    {
		goal=goal.father;
		Point2D p=new Point2D(goal.x, goal.y);
		st.push(p);
	    }
	return st;
    }


    //Fonction crade de débogage
    //Elle est commentée pour montrer qu'elle sert à rien XD
    /*private void afficherMap()
    {
	System.out.println();
	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    this.map[j][i].afficherCase(false,false,true,false,false,false,false,false,false);
		System.out.println("");
	    }
	System.out.println("");


	System.out.println();
	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    this.map[j][i].afficherCase(false,false,false,true,false,false,false,false,false);
		System.out.println("");
	    }
	System.out.println("");


	System.out.println();
	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    this.map[j][i].afficherCase(false,false,false,false,false,true,false,false, false);
		System.out.println("");
	    }
	System.out.println("");

	System.out.println();
	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    this.map[j][i].afficherCase(false,false,false,false,false,false,true,false, false);
		System.out.println("");
	    }
	System.out.println("");

	System.out.println();
	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    this.map[j][i].afficherCase(false,false,false,false,false,false,false,true, false);
		System.out.println("");
	    }
	System.out.println("");

	System.out.println();
	for(int i=0; i<this.hauteur; i++)
	    {
	    	for(int j=0; j<this.largeur; j++)
		    this.map[j][i].afficherCase(false,false,false,false,false,false,false,false,true);
		System.out.println("");
	    }
	System.out.println("");

	}*/

    public static void main(String[]args)
    {
	//Décommenter tout ca pour avoir un test 
	/*int Obstacles[]={6,1,6,2,6,3};
	Path p=new Path(9,4, Obstacles);
	Case start=p.map[3][1];
	Case goal=p.map[7][3];

	p.Path(start, goal);
	p.afficherSolution(start, goal);*/

	int Obstacles[]={4,0,2,1,4,2,5,2,6,2,7,2,0,3,1,3,2,3,3,3,4,3,4,4,6,4,6,5};
	Path p=new Path(9,6, Obstacles);
	Case start=p.map[0][4];
	Case goal=p.map[0][0];

	p.Path(start, goal);
	p.afficherSolution(start, goal);


    }
}
